For data transmission in bandwidth-constrained environments, it is desirable to compress the original data before such transmissions take place. There are two procedures for data compression: lossless and lossy. Lossy procedures often result in better compression ratios than lossless schemes since some of the original data may be discarded. For lossy procedures, either dominant features of the original data or compact representations thereof in other bases are sought. The amount and type of discarded information are dictated by the metric of choice in the compression algorithm.
In basis pursuit (See, for example, S. S. Chen, D. L. Donoho, and M. A. Saunders, Atomic Decomposition by Basis Pursuit, SIAM J. Sci. Comput., vol. 20, no. 1, pp. 33-61, (1999); D. L. Donoho, Compressed Sensing. IEEE Trans. Inform. Theory, vol. 52, pp. 1289-1306 (April 2006); and U.S. Pat. No. 7,646,924, which issued to David L. Donoho on Jan. 12, 2010), the sparsest (i.e., minimizing the ∥•∥1, or standard l1, norm) representation of the original data in a selection of bases is sought. The discarded information follows metrics such as the ∥•∥p norm, where 1≦p≦∞ with p=2 and p=∞ being the most common used values. The resulting problem may be implemented using a standard linear programming or convex programming procedure, and therefore may be solved using available computational techniques.
Basis pursuit is a method involving sparse representation of a vector bεm using an over-complete dictionary of basis vectors, Aεm×n. Specifically, given a matrix Aεm×n, with m<n, it is of interest to find an xεn such that Ax=b. There are many such solutions x and the principle is again to choose the solution that is the sparsest. Note that while x is high dimensional, A can be chosen so that x has very few non-zero entries and therefore x can be transmitted efficiently. Mathematically, basis pursuit aims to solve the problem as in:
                                          min            x                    ⁢                                                  x                                      1                          ⁢                                  ⁢                                            such              ⁢                                                          ⁢              that              ⁢                                                          ⁢              Ax                        =            b                    ,                                          ⁢          or                                    (        1        )                                                      min            x                    ⁢                                                  x                                      1                          ⁢                                  ⁢                                            such              ⁢                                                          ⁢              that              ⁢                                                          ⁢                                                                                      Ax                    =                    b                                                                    p                                      ≤            ɛ                    ,                                    (        2        )            where 1≦p≦∞ (with p=2 and p=∞ being the most common used values) and ε is an error tolerance.
One of available computational techniques is as follows: Instead of solving (1), the following unconstrained problem is investigated:
                                          min            x                    ⁢                                                  x                                      1                          +                              μ            2                    ⁢                                                                                      Ax                  -                  b                                                            2              2                        .                                              (        3        )            As μ approaches ∞, the solution to (3) approaches a solution to (1). Now (3) may be rewritten as the constrained optimization problem
                                          min            x                    ⁢                                                  d                                      1                          +                              μ            2                    ⁢                                                                                    A                  ⁢                                                                          ⁢                  x                                -                b                                                    2            2                                              (        4        )                            such that d=x.Using the Lagrangian multiplier argument again, the solution to the following unconstrained problem:        
                                                        min              x                        ⁢                                                          d                                            1                                +                                    μ              2                        ⁢                                                                                                A                    ⁢                                                                                  ⁢                    x                                    -                  b                                                            2              2                                +                                    λ              2                        ⁢                                                                            d                  -                  x                                                            2              2                                      ,                            (        5        )            approaches one that solves (1) as both μ and λ approach ∞.
By following the argument on “adding back the noise” (so that μ and λ need not be extremely large) as discussed in T. Goldstein and S. Osher, The Split Bregman Method for l1 Regularized Problems, UCLA CAM Report 08-29, and the references cited therein, it can be shown that (5) is equivalent to
                              (                                    x                              k                +                1                                      ,                          d                              k                +                1                                              )                ←                              arg            ⁢                                                  ⁢                                          min                                  x                  ,                  d                                            ⁢                                                                  d                                                  1                                              +                                    μ              2                        ⁢                                                                                                A                    ⁢                                                                                  ⁢                    x                                    -                  b                                                            2              2                                +                                    λ              2                        ⁢                                                                            d                  -                  x                  -                                      b                    k                                                                              2              2                                                          (        6        )                                          where          ⁢                                          ⁢                      b                          k              +              1                                      ←                              b            k                    +                      x                          k              +              1                                -                                    d                              k                +                1                                      .                                              (        7        )            Using the fact that the l1 and l2 components of the objective functional have been “split,” (6) can be solved in two steps:
                              x                      k            +            1                          ←                              arg            ⁢                                                  ⁢                                          min                x                            ⁢                                                μ                  2                                ⁢                                                                                                                        A                        ⁢                                                                                                  ⁢                        x                                            -                      b                                                                            2                  2                                                              +                                    λ              2                        ⁢                                                                                                d                    k                                    -                  x                  -                                      b                    k                                                                              2              2                                                          (        8        )                                          where          ⁢                                          ⁢                      d                          k              +              1                                      ←                              arg            ⁢                                                  ⁢                                          min                d                            ⁢                                                                  d                                                  1                                              +                                    λ              2                        ⁢                                                                                                  d                    -                                          x                                              k                        +                        1                                                              -                                          b                      k                                                                                        2                2                            .                                                          (        9        )            
(7)-(9) are known as the Split Bregman algorithm and solving the two resulting optimization problems of (8) and (9), are simpler. For the problem in the first step, it will be shown hereinbelow as part of the present invention that a closed-form solution to this problem with special consideration for A may be obtained. For the problem in the second step, since there is no coupling between the elements of d, the optimal value of d can be computed explicitly using shrinkage operators as follows:
                                          d                          k              +              1                                ←                      shrink            ⁡                          (                                                                    y                                          k                      +                      1                                                        +                                      b                    k                                                  ,                                  1                  λ                                            )                                      ,                            (        10        )            where shrink (x,μ) is defined as follows:
                              shrink          ⁡                      (                          x              ,              μ                        )                          =                  {                                                                                          x                    -                    μ                                    ,                                                                                                  if                    ⁢                                                                                  ⁢                    x                                    >                  μ                                                                                                      0                  ,                                                                                                  if                    -                    μ                                    ≤                  x                  ≤                  μ                                                                                                                          x                    +                    μ                                    ,                                                                                                  if                    ⁢                                                                                  ⁢                    x                                    <                  μ                                                                                        (        11        )            
In “Morse description and geometric encoding” (See A. Solé, V. Caselles, G. Sapiro and F. Arándiga, Morse Description and Geometric Encoding of Digital Elevation Maps. IEEE Transactions in Image Processing, vol. 13, num. 9, pp. 1245-1262, 2004), Morse-topological and drainage structures for basic geometric description of the original data is first computed, and the missing data may be interpolated from these features using a number of models. To control the quality of the compression, the resulting compressed representation of the original data is accompanied by residuals (that is, the difference between the original data and the resulting compressed representation) which are determined using the ∥•∥∞ norm.